\chapter{Permasalahan dan Struktur Data}


\begin{small}

\section*{Tujuan Pembelajaran:}

\begin{itemize}
\item Memberikan pemahaman tentang berbagai jenis algoritma dalam pemrograman
\item Memberikan pemahaman tentang berbagai struktur data yang ada dalam pemrograman
\end{itemize}


\section*{Setelah menyelesaikan modul ini mahasiswa diharapkan dapat:}

\begin{itemize}
\item Menyebutkan berbagai jenis permasalahan dalam pemrograman
\item Menjelaskan ciri Permasalahan Pengurutan, Pencarian, Pemrosesan String dan Permasalahan Kombinatorial
\item Menjelaskan berbagai Permasalahan yang ada pada Graph, Perhitungan Numerik dan Geometri
\item Menyebutkan Tipe Data Abstrak yang dapat direpresentasikan dengan struktur data linier
\item Menyebutkan jenis-jenis Graph dan Tree dengan berbagai atribut yang melekat
\item Menyebutkan sifat-sifat Set dan Dictionary
\end{itemize}


\section*{Kata kunci:}

Antrian, Dictionary, Graph, Kombinatorial, Pemrosesan String, Pencarian, Pengurutan, Set, Tree, Tipe Data Abstrak, Tumpukan.

\bigskip

\end{small}


\section{Pendahuluan}

Algoritma dan struktur data merupakan dua hal mutlak yang harus dikuasai oleh seseorang yang ingin menyelesaikan masalah-masalah komputasi. Hal ini berarti bahwa setiap orang yang akan membuat program harus paham akan masalah yang dihadapinya, kemudian berdasarkan pemahaman masalah tersebut dia harus dapat membuat langkah-langkah pemecahan masalah dalam bentuk algoritme. Berdasarkan algoritme tersebut selanjutnya dia dapat menulis sebuah program sebagai implementasi untuk memecahkan masalah yang diberikan.

Dalam merancang langkah-langkah pemecahan masalah, seorang pemrogram juga harus tahu struktur data apa yang paling cocok digunakan untuk memecahkan masalahnya. Sebagai contoh, struktur data \emph{linked-list} dengan menggunakan \emph{array} kurang cocok digunakan jika jumlah data yang diolah sering berubah jumlahnya secara dinamis. Seorang pemrogram juga harus paham dengan baik bagaimana cara mengorganisasikan (menstrukturkan) data yang diolahnya.

Suatu program yang baik pada umumnya bersifat modular, yaitu terdiri atas fungsi-fungsi yang merupakan komponen fungsional terkecil dari program tersebut. Fungsi-fungsi yang diperlukan pada suatu program diturunkan dari analisa dan perancangan algoritma secara terstruktur. Mengingat bahwa inti masalah akan terletak pada blok pemecahan masalah, maka seringkali pembahasan algoritma dibatasi hanya pada algoritma blok pemecahan masalah.

Berdasarkan hal tersebut maka dalam modul ini diuraikan berbagai masalah dan juga struktur data yang sangat lazim ditemui dalam pembahasan pemrograman.


\section{Jenis-jenis Permasalahan}

Secara teoritis jumlah masalah yang dapat dibuat menjadi program adalah tak terhingga banyaknya, namun demikian bila dikelompokkan, masalah-masalah tersebut dapat dikategorikan menjadi beberapa jenis, yaitu Permasalahan Pengurutan, Permasalahan Pencarian, Permasalahan Pemrosesan String, Permasalahan Graph, Permasalahan Kombinatorial, Permasalahan Geometri dan Permasalahan Numerik

\subsection{Permasalahan pengurutan}

Permasalahan pengurutan merupakan permasalahan untuk membuat sekelompok data yang tersusun secara acak sebagai masukan (input), menjadi sekumpulan data yang beraturan, yaitu merupakan daftar yang tersusun dari kecil ke besar (ascending) atau sebaliknya dari besar ke kecil (descending), sebagai keluaran (output).

Seringkali data yang akan diurutkan merupakan sekumpulan data yang terdiri atas beberapa item data (atribut, field). Dalam hal demikian, pengurutan data dilakukan berdasarkan salah satu item data tersebut yang disebut sebagai \emph{key}. Data yang telah diurutkan pada umumnya lebih mudah untuk dimanfaatkan, misal dalam pencarian suatu data.

Sampai dengan saat ini telah banyak algoritma yang dapat dipergunakan untuk mengurutkan data. Di antara algoritma tersebut dapat dibedakan berdasarkan sifatnya yaitu dalam hal penggunaan tambahan memori dan dalam hal kestabilan hasil pengurutan. Algoritma pengurutan yang tidak memerlukan tambahan memori dalam proses pengurutannya disebut  sebagai algoritma pengurutan yang bersifat \emph{in place}. Dalam hal kestabilan suatu algoritma dikatakan stabil apabila urutan data yang bernilai sama tidak berubah, yaitu bila sebelum dilakukan proses pengurutan \(a_j\) terletak lebih dahulu daripada \(a_k\), maka setelah pengurutan \(a_j\) juga harus terletak lebih dahulu daripada \(a_k\).

\subsection{Permasalahan pencarian}

Permasalahan pencarian merupakan permasalahan untuk mencari sebuah data dalam sekelompok data tertentu. Apabila data yang diinginkan merupakan suatu data yang terdiri atas beberapa item data (atribut, field), maka pencarian dilakukan berdasarkan salah satu item data yang disebut sebagai \emph{key}.

Untuk menyelesaikan masalah ini telah terdapat banyak algoritma pencarian yang mempunyai karakteristik yang berbeda. Hal penting yang perlu diperhatikan dalam masalah pencarian ini adalah cara mengorganisasikan data tersebut, khususnya apabila dalam data yang dipergunakan tersebut seringkali ditambah atau dihapus.

\subsection{Permasalahan pengolahan string}

String merupakan sekumpulan karakter. Dua jenis string yang sering diproses dalam suatu algoritma adalah teks string dan bit string. Teks string adalah sekumpulan karakter teks yang terdiri atas huruf, symbol angka dan karakter khusus lainnya, sedangkan bit string adalah sekumpulan symbol 0 (nol) dan 1 (satu).

Salah satu masalah penting dalam pemrosesan string adalah masalah pencocokkan string (\emph{string matching}). Dalam hal ini ingin diketahui apakah pola string yang diketahui ada pada suatu kumpulan string tertentu.

\subsection{Permasalahan graph}

Secara fisik graph merupakan kumpulan beberapa \emph{vertex} (digambarkan dengan bentuk lingkaran atau elips) dan edge (digambarkan sebagi garis) yang menghubungkan vertex-vertex tersebut. Graph dapat merepresentasikan berbagai fasilitas nyata yang ada seperti jaringan komunikasi, jaringan listrik ataupun jalan raya yang menghubungkan berbagai tempat.

Berbagai masalah yang ada dalam graph antara lain adalah: melakukan kunjungan (\emph{traversing}) ke setiap vertex secara sistematis, mencari jarak terdekat antara vertex yang satu dengan yang lain, mencari total jarak edge yang dapat menghubungan setiap vertex.

\subsection{Permasalahan kombinatorial}

Permasalahan kombinatorial merupakan salah satu permasalahan yang kompleks. Dalam memecahkan masalah kombinatorial, algoritma yang ada pada umumnya memerlukan waktu yang lama. Penulisan kombinasi susunan suatu obyek dan pencarian seluruh himpunan bagian dari suatu himpunan merupakan contoh dari permasalahan yang bersifat kombinatorial.

\subsection{Permasalahan geometri}

Algoritma dalam permasalahan geometri berhubungan dengan obyek-obyek geometri seperti titik, garis dan poligon yang banyak dipergunakan dalam pengetahuan grafika komputer.

Dua masalah klasik dalam permasalahan geomentri adalah pencarian dua titik yang mempunyai jarak terdekat di antara sekumpulan titik yang telah diketahui letaknya dan menentukan garis-garis terluar yang dapat ditarik dari sekumpulan titik (\emph{convex hull}).

\subsection{Permasalahan numerik}

Permasalahan numerik adalah permasalahan untuk mencari solusi persoalan matematika dengan menggunakan program yang dijalankan pada suatu komputer. Berbagai algoritma permasalahan numerik akan sangat diperlukan oleh para ahli keteknikan untuk menyelesaikan masalah yang dihadapinya. Permasalahan numerik dasar yang diperlukan antara lain adalah: pencarian solusi dari suatu sistem persamaan, menghitung nilai integral tentu, dan lain-lain.


\section{Representasi Struktur Data}

Agar suatu algoritma dapat dituliskan sebagai suatu program komputer, data yang akan dimanipulasi perlu diorganisasikan dalam struktur data yang dimengerti oleh bahasa pemroraman yang dipergunakan.

Dalam setiap bahasa pemrograman tersedia berbagai jenis tipe data (data type) yang dapat dimanipulasi dan pada umumnya tersedia pula fasilitas untuk mengorganisasikan berbagai jenis data tersebut, sehingga menjadi suatu data yang terstruktur. 

Suatu model data yang ada dalam bayangan atau abstraksi pemrogram disebut sebagai sebagai tipe data abstrak (abstract data type) yang bila ingin dimanipulasikan dalam suatu program, perlu dibuat dengan menggunakan fasilitas yang ada pada bahasa pemrograman yang dipergunakan.

Struktur data yang sering dipakai dalam berbagai algoritma tersebut antara lain adalah: struktur data linier, yang dapat dibedakan atas daftar (list), tumpukan (stack) dan antrian (queue), graph, tree, himpunan (set) dan kamus (dictionary).

\subsection{List}

List atau daftar merupakan tipe data abstrak yang bersifat fleksibel, yaitu isi dari daftar dapat bertambah atau berkurang sesuai kebutuhan. Selain penambahan dan pengurangan operasi-operasi yang sering dilakukan pada suatu daftar antara lain adalah penghitungan jumlah anggota suatu daftar, pencarian anggota pada daftar dan juga penggabungan dua buah daftar. Seringkali pada sebuah daftar diinginkan keteraturan tertentu berdasarkan key dari anggota-anggotanya. Hal yang demikian dapat dilakukan dengan menyusun (sort) list tersebut sehingga menjadi suatu daftar yang terurut (sorted list).

Dalam implementasinya suatu daftar dapat dibuat dengan menggunakan struktur data array yang bersifat statis ataupun dengan menggunakan struktur data dinamis (daftar terkait atau linked list). Pendeklarasian daftar sebagai array membuat daftar tersebut terbatas dalam jumlah anggota dan juga memerlukan operasi pergeseran anggota bila ingin dilakukan pengurangan anggota. Bentuk suatu daftar yang diimplementasikan dengan struktur data statis diperlihatkan pada Gambar~\ref{fig:implementasi-list-statis}.

Implementasi List dengan array kadang disertai dengan informasi informasi mengenai jumlah anggota yang ada pada List tersebut. Biasanya informasi jumlah data ini disimpan sebagai elemen pertama dalam array. Jika hal ini dilakukan, maka bilangan pertama dalam List dapat diketahui berada pada indeks ke-1, sedangkan bilangan terakhir dalam List dapat ditemukan pada indeks ke-$p$, di mana $p$ menunjukkan jumlah bilangan yang tersimpan dalam array. Nilai $p$ maksimum sesuai dengan jumlah elemen dalam array ketika array tersebut dideklarasikan di dalam program.

\begin{figure}
%Gambar list statis; Ada beberapa kotak kosong yang nantinya digunakan untuk isi data; di bawah masing-masing kotak ada label mulai dari 0 sampe n-1; trus ada satu kotak khusus di atas kotak berlabel 0, labelnya Jumlah Anggota; paling atas sendiri ada label List.
\begin{center}
\includegraphics{list-statis}
\end{center}
\caption{Implementasi list secara statis} \label{fig:implementasi-list-statis}
\end{figure}

Implementasi daftar dengan menggunakan struktur data dinamik (dynamic data structure) yaitu daftar terkait (linked list) memerlukan tipe data struktur di mana satu di antara elemennya merupakan pointer kepada tipe data tersebut atau self referential. Anggota dari daftar terkait disebut sebagai node. Beberapa operasi penting untuk tipe data abstrak daftar terkait antara lain adalah: inisialisasi, pencarian node, penambahan node di muka node yang diketahui dan penghapusan node di muka node yang diketahui.

Sejara lojik suatu daftar terkait digambarkan sebagai rangkaian node. Node merupakan struktur dengan minimal elemen adalah elemen info (dapat merupakan struktur data yang terdiri atas berbagai tipe data) dan next yang merupakan pointer untuk tipe data node tersebut.

Identifier yang dipergunakan untuk menunjukkan suatu daftar terkait (head dari daftar terkait) dapat merupakan suatu pointer kepada node atau node itu sendiri. Dalam modul ini akan dipergunakan cara kedua yaitu head merupakan suatu node yang elemen infonya tidak dipergunakan. Dengan demikian suatu daftar terkait kosong (empty linked list) merupakan sebuah node dengan element next yang berisi NULL pointer. Elemen next dari head menunjuk pada elemen pertama, next dari elemen pertama menunjuk pada elemen kedua, demikian seterusnya hingga elemen terakhir yang nextnya menunjuk pada NULL. Contoh suatu linked list yang berisi dua buah node dan dan juga suatu empty list dapat dilihat pada Gambar~\ref{fig:linked-list}.

\begin{figure}
%gambar sebuah singly-linked-list berisi head dan dua cell-info. satu lagi di sebelah kanan ada satu empy linked-list.
  \begin{center}
	\subfigure{
    \includegraphics{singly-linked-list}
	} \label{fig:linked-list}
	
	\subfigure{
    \includegraphics{singly-linked-list-empty}
	} \label{fig:linked-list-empy}
	\end{center}	
\caption{Bentuk Linked List dan Empty Linked List} \label{fig:linked-list}
\end{figure}

\subsection{Stack}

Stack atau tumpukan merupakan daftar yang bersifat khusus, yaitu anggotanya hanya dapat ditambah dan dikurangi melalui satu sisi yang biasa disebut sebagai TOP. Proses penambahan suatu tumpukan dikenal sebagai PUSH, sedangkan pengurangan anggota disebut POP. Sifat yang mengeluarkan anggota yang masuk terakhir, menyebabkan tumpukan juga dikenal sebagai tipe data abstrak yang bersifat LIFO (Last In First Out). Karena tumpukan merupakan daftar yang bersifat khusus, maka seperti halnya List implementasi tumpukan dapat dilakukan baik dengan cara statis maupun dengan cara dinamis.

Representasi secara statis dari stack akan memerlukan suatu elemen tambahan bertipe integer yang berfungsi untuk menyatakan tempat dari anggota terakhir yang masuk (top).

Proses POP akan mengurangi isi tumpukan, oleh karena itu untuk menghindari kesalahan, maka sebelum proses tersebut dilakukan tumpukan perlu dicek terlebih dahulu apakah kosong atau tidak. Bila kosong maka POP tidak dilakukan. Dalam proses PUSH, bila dipergunakan struktur data statis, maka perlu dilakukan pengecekan apakah tumpukan tersebut penuh atau tidak. Bila penuh maka proses PUSH tidak dilakukan. Oleh karena itu dalam suatu stack perlu dibuat fungsi yang dapat mengetahui tumpukan tersebut penuh atau kosong.

\subsection{Queue}

Seperti halnya tumpukan, queue atau antrian juga merupakan daftar yang bersifat khusus, yaitu penambahan anggota hanya dapat dilakukan melalui satu sisi yang disebut REAR (belakang), sedangkan pengurangan anggota hanya dapat dilakukan melalui sisi lain yang disebut FRONT (depan). Proses penambahan suatu antrian dikenal sebagai ENQUEUE, sedangkan pengurangan anggota disebut DEQUEUE. Karena sifatnya tersebut antrian juga dikenal sebagai tipe data abstrak yang bersifat FIFO (First In First Out).

Proses DEQUEUE akan mengurangi isi antrian, oleh karena itu untuk menghindari kesalahan, maka sebelum proses tersebut dilakukan antrian perlu dicek terlebih dahulu apakah kosong atau tidak. Bila kosong maka DEQUEUE tidak dilakukan. Dalam proses ENQUEUE, bila dipergunakan struktur data statis, maka perlu dilakukan pengecekan apakah antrian tersebut penuh atau tidak. Bila penuh maka proses ENQUEUE tidak dilakukan. Oleh karena itu dalam suatu antrian perlu dibuat fungsi yang dapat mengetahui tumpukan tersebut penuh atau kosong.

Queue dapat direpresentasikan secara statis dan dinamis. Dalam hal representasi statis maka akan memerlukan dua elemen tambahan bertipe integer yang berfungsi untuk menyatakan tempat awal dan akhir yang ditempati oleh isi queue.

\subsection{Graph} \label{sect:graf}

Graph merupakan Tipe Data Abstrak yang terdiri atas himpunan vertex \(V\) dan himpunan edge \(E\). Vertex biasa digambarkan dengan lingkaran kecil, sedangkan edge adalah garis yang menghubungkan antara dua vertex. Graph \(G\) yang terdiri atas himpunan vertex \(V\) dan himpunan edge \(E\) seringkali ditulis dengan notasi  \(G = (V,E)\).

Vertex pada suatu graph biasa diberi nama dengan karakter ataupun angka seperti: \(a, 1, x, 2, v\) dan \(v_1\), sedangkan edge dapat diberi nama tersendiri seperti: \(e_1, e_2, \ldots\) atau merupakan gabungan antara dua vertex yang terhubung padanya seperti: \((a,b), (p,q), (u,v) \ldots\)

Suatu peta jalan raya yang menghubungkan kota-kota yang ada pada peta tersebut merupakan suatu graph dimana kota merupakan vertex dan jalan hubung antar kota tersebut merupakan edge. Demikian juga jaringan listrik atau komunikasi antar kota-kota tersebut dapat dipandang sebagai suatu graph.

\begin{figure}
%place dots from left to right and down (like matrices) in this order: row1: 1, 2, 3, 4; row2: 5, 6, 7. Connect 1 with 2 and 5; 2 with 5; 5 with 6; 3 with 7.
  \begin{center}
    \includegraphics{graph-undirected}
  \end{center}
\caption[Graph tak berarah $G1$]{Graph tak berarah $G1=(V,E)$ dengan $V=\{1,2,3,4,5,6,7\}$ dan $E=\{(1,2),(1,5),(2,5),(5,6),(3,7)\}$ } \label{fig:graf-tak-berarah}
\end{figure}

\begin{figure}
%modifikasi graf fig:graf-tak-berarah dengan tambahan arah berikut ini: 1 ke 2; 2 ke 1; 3 ke 3; 4 ke 3; 5 ke 1 dan 2; 6 ke 2 dan 5; 7 ke 3.
  \begin{center}
    \includegraphics{graph-directed}
  \end{center}
\caption[Graph berarah $G2$]{Graph berarah $G2=(V,E)$ dengan $V=\{1,2,3,4,5,6,7\}$ dan $E=\{(1,2),(2,1),(3,3),(4,3),(5,1),(5,2),( 6,2),( 6,5),(7,3)\}$} \label{fig:graf-berarah}
\end{figure}

\subsubsection{Graph berarah dan tidak berarah}

Edge pada suatu graph dapat mempunyai arah maupun tidak. Bila edge pada suatu graph mempunyai arah maka graph tersebut disebut sebagai graph berarah (directed graph), sedangkan bila edge tidak berarah maka graph tersebut disebut sebagai graph tak berarah (undirected graph) yang seringkali cukup disebut sebagai graph saja. Contoh suatu graph tak berarah dan berarah digambarkan pada Gambar~\ref{fig:graf-tak-berarah} dan Gambar~\ref{fig:graf-berarah}.

Pada graph berarah, penulisan nama edge yang menggunakan gabungan vertex, harus urut sebagai \((u,v)\) dimana \(u\) adalah vertex tempat edge \((u,v)\) berasal dan \(v\) adalah vertex dimana edge \((u,v)\) berakhir. Hal tersebut mengakibatkan edge \((v,w)\) merupakan edge yang berbeda dengan edge \((w,v)\). Pada graph tidak berarah urutan penulisan vertex untuk nama edge boleh dipertukarkan, karena edge \((v,w)\) adalah edge yang sama dengan edge \((w,v)\). Pada graph berarah bisa terdapat edge yang berawal dan berakhir pada vertex yang sama, seperti \((v,v)\) yang disebut self-loop. Hal tersebut tidak dikenal pada graph tak berarah.

Pada graph tak berarah suatu edge dikatakan ber-\emph{incident} pada kedua vertex yang terhubung padanya. Pada graph berarah, edge yang berasal dari suatu vertex dikatakan \(incident from\) vertex tersebut sedangkan edge yang berakhir pada suatu vertex dikatakan \(incident to\) vertex tersebut.

\emph{Degree} suatu vertex pada grap tak berarah adalah jumlah edge yang berincident kepada vertex tersebut. Pada graph berarah suatu degree dari suatu vertex dibedakan atas \emph{in-degree} yaitu jumlah edge yang berarah menuju (incident to) vertex tersebut dan \emph{out-dgeree} yaitu jumlah edge yang berarah meninggalkan (incident from) vertex tersebut.

\subsubsection{Graph berbobot dan tidak berbobot}

Pada suatu graph, edge dapat mempunyai bobot yang sama maupun berbeda. Hal tersebut mengakibatkan graph (baik berarah maupun tidak) dapat dibedakan menjadi graph berbobot (weighted graph) dan graph tidak berbobot (unweighted graph). Baik Gambar~\ref{fig:graf-tak-berarah} dan~\ref{fig:graf-berarah} merupakan graph tanpa bobot, sedangkan Gambar~\ref{fig:graf-berbobot} merupakan contoh graph dengan bobot.

\begin{figure}
%gambarkan graf dengan 4 verteks (matriks 2 kali 2): a, b, c, d. Bobot a-b = 5; a-c = 4; b-c = 8; b-d = 7.
  \begin{center}
    \includegraphics{graph-weighted}
  \end{center}
\caption{Graph berbobot} \label{fig:graf-berbobot}
\end{figure}

\subsubsection{Path dan cycle}

Path atau lintasan merupakan urutan edge yang menghubungkan satu vertex ke vertex lain. Bila jumlah urutan edge tersebut adalah \(k\), maka dikatakan lintasan tersebut mempunyai panjang lintasan (length) \(k\). Suatu lintasan yang berasal dan berakhir pada vertex yang sama disebut cycle (lintasan tertutup). Suatu graph yang memiliki lintasan tertutup disebut cyclic graph, bila tidak disebut sebagai acyclic graph. Graph berarah yang tidak mempunyai lintasan tertutup dikenal sebagai directed acyclic graph (DAG).

Bila ada lintasan dari vertex \(u\) ke \(v\), maka dikatakan bahwa vertex \(v\) dapat dicapai (reachable) dari vertex \(u\) dan bila panjang lintasan tersebut adalah \(1\), yaitu ada edge \((u,v)\), maka dikatakan bahwa \(v\)  adjacent dengan \(u\).

Pada graph berarah dapat terjadi tetapi \(u\) tidak adjacent pada \(v\) meskipun \(v\) adjacent pada \(u\) (karena ada edge \((u,v)\) tetapi tidak ada \((v,u)\) ). Karena pada graph tak berarah edge \((u,v)\) sama dengan \((v,u)\), maka bila \(u\) beradjacent dengan \(v\), pastilah \(v\) beradjacent dengan \(u\). Dengan perkataan lain dikatakan bahwa hubungan adjacent bersifat simetris pada graph tak berarah, tetapi tidak pada graph berarah.

Suatu graph tak berarah dikatakan terhubung (connected) apabila setiap vertex pada graph tersebut dapat dicapai dari setiap vertex yang lain (mempunyai path). Suatu graph yang tidak terhubung (ada vertex yang tidak dapat dicapai dari vertex lain) dapat dipandang sebagai graph yang terdiri atas beberapa komponen subgraph yang terhubung. Pada graph berarah, bila setiap vertex dapat dicapai dari setiap vertex lain, maka graph tersebut dikatakan sebagai graph terhubung kuat (strongly connected).

\subsubsection{Representasi graph}

Dalam pemrograman graph dapat direpresentasikan sebagai matriks (array dua dimensi) yang biasa dikenal sebagai adjacency matrix maupun array dari daftar terkait yang biasa dikenal sebagai adjacency list.

\paragraph{Adjacency matrix}

Pada adjacency matrix, matriks \(M\) yang merepresentasikan graph merupakan matriks bujur sangkar \(n \times n\), dimana \(n\) adalah jumlah vertex pada graph tersebut. Untuk unweighted graph, isi dari matriks tersebut menyatakan apakah vertex pada baris ber-adjacent dengan vertex pada kolom. Pada umumnya dipergunakan bilangan integer \(1\) untuk menyatakan ber-adjacent dan bilangan integer \(0\) untuk tidak. Bila graph merupakan weighted graph, pada umumnya isi dari matriks \(M_{i,j}\) tersebut dimaksudkan untuk merepresentasikan weight (bobot) dari edge \((i,j)\). Matriks untuk graph tak berarah akan bersifat simetris sedangkan untuk graph berarah tidak.

\paragraph{Adjacency list}

Adjacency list merupakan struktur data yang dapat merepresentasikan tipe data abstrak dengan lebih fleksibel. Struktur data ini merupakan array dari struktur vertex. Struktur vertex merupakan head dari daftar terkait struktur edge yang ber-adjacent kepada vertex tersebut. Pada struktur edge harus terdapat elemen pointer yang dapat menunjuk struktur edge (self referential).

\subsection{Tree}

Suatu graph tak berarah yang tidak memiliki cycle disebut sebagai forest. Bila graph tersebut merupakan graph terhubung maka forest tersebut dikatakan sebagai free tree. Vertex pada suatu forest atau free tree disebut juga sebagai node. Bila salah satu dari node pada free tree diperlakukan khusus sebagi root, yaitu dianggap sebagai asal dari semua node yang ada, maka free tree tersebut disebut sebagai rooted tree. Bila tidak dirinci lebih lanjut, pada umumnya yang dimaksud dengan tree adalah rooted tree.

Pada tree, edge atau hubungan antara node diartikan sebagai hubungan orang tua dengan anak (parent - child). Dengan demikian setiap node (kecuali root) selalu mempunyai satu node lain yang merupakan orang tuanya dan dapat mempunyai beberapa node lain sebagai anaknya. Node yang tidak mempunyai anak disebut sebagai \emph{leaf} atau \emph{external node}, sedangkan dua atau lebih node yang mempunyai orang tua yang sama disebut sebagai \emph{sibling}.

Bila urutan dari anak-anak suatu node dianggap penting, maka tree tersebut disebut sebagai \emph{ordered tree} dan pengidentifikasian anak-anak node tersebut dilakukan terurut dari kiri ke kanan, dimana anak terkiri (\emph{left most child}) dianggap sebagai anak tertua (\emph{oldest child} atau \emph{oldest sibling}).

\emph{Degree} dari suatu node pada tree adalah sebanyak anak node tersebut (bandingkan dengan \emph{degree} pada graph). Panjang path dari root ke suatu node disebut sebagai \emph{depth} dari node tersebut, sedangkan \emph{height} dari suatu tree adalah maksimum \emph{depth} yang ada pada tree tersebut.

\begin{figure}
place these vertex in 3 rows: a, b, c, d; e, f, g, h; i, j, k. Connect a with b, e, and f; e with i; f with j. Connect g with c, h, and k; d with h.
\caption{Forest terdiri atas dua buah Free Tree} \label{fig:forest}
\end{figure}

\begin{figure}
place these vertices in 3 rows: a; b, c, d, e; f, g, h, i, j, k. Connect a with b c d e. Connect b with f. Connect c with g h. Connect e with i j k.
\caption{Tree (Rooted Tree)} \label{fig:rooted-tree}
\end{figure}

\subsubsection{Binary Tree}

Suatu tree yang setiap node maksimum mempunyai dua anak, di mana bila ada anak tersebut dapat dibedakan menjadi anak kiri (left child) dan anak kanan (right child) disebut binary tree. Dengan menggunakan cara rekursif, suatu binary tree dapat didefinisikan secara formal sebagi berikut:

\begin{quote}
Suatu binary adalah suatu tree yang tidak memiliki node (empty tree), atau terdiri atas tiga kelompok terpisah node yang terdiri atas sebuah root, binary tree yang merupakan left subtree dan binary tree lain yang merupakan right subtree.
\end{quote}

\begin{figure}
draw a binary tree with root 1, children 2 and 3. Node 2 has children 4 and 5. Node 3 has right child 6. Node 5 has left child 7.
\caption{Binary Tree} \label{fig:binary-tree}
\end{figure}

Meskipun mempunyai struktur yang sama dengan ordered tree dengan maksimum degree dua, binary tree berbeda dengan ordered tree tersebut. Pada binary tree, suatu node yang merupakan anak tunggal dapat dibedakan apakah anak tersebut adalah anak kiri atau anak kanan, sedangkan pada ordered tree yang maksimum mempunyai degree dua, anak tunggal tidak dapat dibedakan. Dengan perkataan lain bila pada ordered tree dengan maksimum degree dua, suatu node dengan dua anak kehilangan oldest child, maka anak yang tinggal akan mengisi posisi tersebut dan menjadi oldest child, sedangkan pada binary tree, bila suatu node dengan dua anak yang kehilangan left child, maka anak yang tinggal tetap dianggap sebagai right child.

Suatu binary yang semua node kecuali \emph{leaf} mempunyai dua anak disebut sebagai \emph{full binary tree}, sedangkan full binary tree yang semua leaf nya mempunyai \emph{level} sama disebut sebagai \emph{complete binary tree} (binary tree lengkap) .

Heap adalah suatu binary tree yang hampir lengkap yaitu semua level terisi penuh dengan node kecuali level terakhir terisi penuh dari kiri ke kanan hingga node terakhir dan key dari parent selalu lebih besar dari atau sama dengan (bisa juga lebih kecil dari atau sama dengan) key dari anak-anaknya. Selanjutnya dalam pembahasan pada buku ini dipergunakan sifat key dari parent yang selalu lebih besar dari atau sama dengan key dari anak-anaknya.

\subsubsection{Positional Tree}

Karena sifatnya yang membedakan antara anak kanan dan anak kiri, suatu binary juga digolongkan sebagai positional tree (membedakan anak berdasarkan posisi). Positional tree yang lain adalah 3-ary tree, 4-ary tree, \(\ldots\) yang secara umum disebut sebagai \(k-ary\) tree, dimana \(k\) adalah degree terbesar yang ada pada tree tersebut. Pengertian full dan complete k-ary adalah serupa dengan full dan complete binary tree.

\subsubsection{Representasi Tree}

Seperti halnya Tipe Data Abstrak lainnya, tree dapat direpresentasikan dengan menggunakan struktur data statik maupun dinamik. Representasi paling sederhana dari suatu tree adalah dengan array sebanyak jumlah node dari bilangan integer, dimana index array menyatakan nomor node sedangkan isi dari array tersebut adalah orangtua dari node tersebut. Hal ini dimungkinkan karena pada tree setiap node hanya mempunyai satu orangtua. Namun demikian implementasi sederhana ini hanya baik untuk melakukan operasi pencarian orangtua dari suatu node, sedangkan operasi lain seperti menentukan anak dan mencari sibling dari suatu node sulit dilakukan dengan cara ini.

Struktur data statik lain yang juga dapat dipergunakan untuk merepresentasikan tree adalah array dengan anggota sebanyak jumlah node dari struktur yang mengacu kepada nomor node yang merupakan oldest child dan next sibling dari node tersebut. Representasi ini baik untuk mencari anak maupun sibling dari suatu node, namun sulit untuk mencari orangtua suatu node.

\subsection{Himpunan (Set) dan Kamus (Dictionary)}

Seperti halnya dalam matematika, himpunan diartikan sebagai kumpulan dari anggota. Anggota himpunan dapat merupakan unsur data yang sederhana (bilangan atau karakter) maupun himpunan lain. Bila dalam matematika suatu himpunan dapat dinyatakan dengan mendeskripsikan ciri yang dimiliki oleh anggotanya, dalam pemrograman suatu himpunan harus dinyatakan dengan cara menyebutkan anggotanya.

Sebagai suatu tipe data abstrak, operasi yang sangat umum dilakukan pada himpunan antara lain adalah: mencari apakah suatu unsur merupakan anggota himpunan, mencari irisan dan gabungan dua atau lebih himpunan.

Kamus merupakan istilah khusus yang diberikan kepada tipe data abstrak yang operasinya terbatas kepada pencarian, penambahan dan pengurangan anggota.


\section{Soal-soal latihan dan bahan diskusi}

\begin{ExerciseList}
  \Exercise Apa yang dimaksud dengan stabil dan ditempat pada algoritma Pengurutan. Jelaskan dengan contoh.
  
  \Exercise Jelaskan dengan contoh perbedaan hasil dari algoritma pengurutan yang stabil dengan yang tidak stabil.
  
  \Exercise Tuliskan perbedaan dan persamaan antara masalah Pencarian dengan masalah Pemrosesan String.
  
  \Exercise Tuliskan kelebihan dan kekurangan representasi List dengan menggunakan struktur data statis dengan dinamis. Berikan contoh deklarasi kedua struktur data tersebut dalam bahasa C dan Java.
  
  \Exercise Dalam sebuah \emph{simple graph} (graf tanpa \emph{cycle} dan tanpa \emph{multiple edge}) yang memiliki $n$ verteks, berapa jumlah \emph{edge} maksimum yang mungkin ada?
  
  \Exercise Dalam sebuah \emph{simple graph} (graf tanpa \emph{cycle} dan tanpa \emph{multiple edge}) yang memiliki $n$ verteks, berapa jumlah \emph{edge} minimum yang diperlukan agar graf tersebut \emph{connected} (terdapat \emph{path} yang menghubungkan antara setiap pasang verteks)?
  
  \Exercise \label{ex:graf-relasional} Sebuah graf juga dapat direpresentasikan dengan menggunakan dua buah tabel dalam basis data relasional. Tabel pertama berisi informasi tentang verteks. Tabel ini berisi setidaknya satu kolom yang menyimpan informasi nama verteks.
  
  Tabel kedua menyimpan relasi antara verteks-verteks di tabel pertama. Tabel ini terdiri setidaknya atas dua kolom. Kolom pertama berisi nama verteks asal, dan kolom kedua berisi nama verteks pasangannya. Hubungan kardinalitas di antara kedua tabel ini adalah sebagai berikut: Tabel verteks berelasi \emph{many-to-many} ke dirinya sendiri. Tabel relasi merupakan tabel perantara yang mengimplementasikan relasi \emph{many-to-many}.
  
  Berdasarkan uraian ini, gambarkan isi tabel verteks dan tabel relasi untuk graf pada Gambar~\ref{fig:graf-tak-berarah}.
  
  \Exercise Lakukan modifikasi terhadap representasi tabel relasional pada Soal~\ref{ex:graf-relasional} untuk graf berarah dan graf berbobot.
  
  Gambarkan isi tabel verteks dan tabel relasi untuk graf-graf pada Gambar~\ref{fig:graf-berarah} dan Gambar~\ref{fig:graf-berbobot}.
  
  \Exercise Apakah keunggulan representasi List dengan menggunakan doubly linked list dengan singly linked list.
  
  \Exercise Deklarasikan struktur data linked list pada Gambar~\ref{fig:linked-list} (di halaman~\pageref{fig:linked-list}). Tuliskan algoritma dari prosedur PUSH dan POP, bila struktur tersebut dipergunakan untuk merepresentasikan tipe data abstrak tumpukan.
\end{ExerciseList}

\begin{Soal}
Deklarasikan struktur data doubly linked list. Dengan menggunakan struktur data tersebut sebagai antrian, tuliskan algoritma dari prosedur ENQUEUE dan DEQUEUE yang diperlukan.
\end{Soal}

\begin{Soal}
Berikan pendapat saudara terhadap pernyataan berikut: "Tree adalah graph yang bersifat khusus". Bila saudara setuju dengan pernyataan tersebut, tunjukkan kekhususan tree dari graph, bila tidak berikan alasan saudara. 
\end{Soal}

\begin{Soal}
Jelaskan berbagai kemungkinan struktur data yang dapat dipergunakan untuk merepresentasikan tree
\end{Soal}

\begin{Soal}
Jelaskan mengapa heap dapat direpresentasikan dengan menggunakan array. 
\end{Soal}

\begin{Soal}
Gambar suatu graph berarah dengan 10 vertex (tentukan sendiri edge yang ada), Selanjutnya gambar representasi graph tersebut dalam adjacency matriks dan adjacency list.
\end{Soal}
